package sjjg.tree;

public class Heap<T extends Comparable> {
    private int N;//记录元素个数
    public T[] heap;
    Heap(int capacity){
        this.heap=(T[]) new Comparable[capacity+1];//为了方便操作 将0索引废弃
        this.N=0;//初始元素个数为0
    }
    private boolean less(int index1,int index2){
        return heap[index1].compareTo(heap[index2])<0;
    }
    private void exchange (int index1,int index2){
            T temp;
            temp=heap[index1];
            heap[index1]=heap[index2];
            heap[index2]=temp;
    }
    private void insert(T t){
        heap[++N]=t;//将元素插入到数组末 即树的最后
        //将插入元素上浮 保证堆的有序
        swim(N);
    }
    private void swim(int k){
        int count=0;
        while (k>1){
            if(less(k/2,k)){
                exchange(k/2,k);
                count++;
            }else if(count==0){//如过是第一次就比父节点小那就没必要再循环了
                return;
            }
            k=k/2;//跳跃到父节点 进入下一次循环
        }
    }
    private T delMax(){

          //删除最大节点即根节点即1位置元素
          T max=heap[1];//暂存max元素
          heap[1]=heap[N];//可以将最后一个元素复制给第一个元素
         //再删除末尾元素
          heap[N]=null;
          //元素数量-1
          N--;
         //让第一个元素下沉 保证堆的有序
         sink(1);
         return max;
    }

    private void sink(int k) {
          while (2*k<=N){
                 int max=0;
                 //判断右节点是否存在
                 if(2*k+1<=N){
                     //找出左子树与右子树的较大者
                     if(less(2*k,2*k+1)){
                         max=2*k+1;
                     }else {
                         max=2*k;
                     }
                 }else {
                     max=2*k;
                 }
               //判断父节点与较大值的大小
              if(less(k,max)){
                  exchange(k,max);
              }else {
                  break;
              }
              k=max;
          }
    }

    public static void main(String[] args) {
        Heap<Character> characterHeap = new Heap<>(10);
        characterHeap.insert('a');
        characterHeap.insert('b');
        characterHeap.insert('c');
        characterHeap.insert('d');
        characterHeap.insert('e');
        characterHeap.insert('f');
        characterHeap.insert('g');
        Character c;
        while ((c=characterHeap.delMax())!=null){
            System.out.print(c+" ");
        }
    }
}
